"""
假设你为一家自动售货机厂家编程序，自动售货机要每次找给顾客最少数量硬币；
    假设某次顾客投进 100元钱，买了 37元的东西，要找 63元，
    那么最少数量就是：1张 50元、 1张 10元 、3张 1元，一共 5张

"""


# 贪心算法
def get_min_coins(money_value: int):  # 贪心版本
    """
    贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。
        也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
    len_current_value: 需要找的张数
    return_list: 已经找的金额张数
    :param money_value: 需要找的金额
    """
    return_list = []
    money_coins = [1, 5, 10, 20, 50, 100]
    money_coins_sorted = sorted(money_coins, reverse=True)
    for current_value in money_coins_sorted:
        len_current_value = money_value // current_value
        return_list += [current_value] * len_current_value
        money_value -= current_value * len_current_value
        '''
        第一次: len_current_value == 0 , return_list = [] , money_value ==  63
        第二次: len_current_value == 1 , return_list = [50] , money_value ==  13
        第三次: len_current_value == 0 , return_list = [50] , money_value ==  13
        第四次: len_current_value == 1 , return_list = [50, 10] , money_value ==  3
        第五次: len_current_value == 0 , return_list = [50, 10] , money_value ==  3
        第六次: len_current_value == 3 , return_list = [50, 10, 1, 1, 1] , money_value ==  0
        '''
        if money_value <= 0:  # 截至条件
            break
    return return_list


# 递归求解
def recMC(coin_value_list, money_value):  # 使用递归求得最优解
    """ 太慢 太low 太拉胯
    递归三条件:
        不断缩小自身规模
        不断调用自身
        有结束条件
    其中,递归是自顶向下进行计算的.
    """
    min_len = money_value
    if money_value in coin_value_list:  # 递归结束条件
        return 1
    else:
        for current_value in [c for c in coin_value_list if c < money_value]:
            now_len = 1 + recMC(coin_value_list, money_value - current_value)  # 调用自身,且缩小规模
            if now_len < min_len:
                min_len = now_len

    return min_len


# 递归优化：备忘录优化
def recDc(coin_value_list, money_value, know_results):  # 递归改进版本
    """
    递归改进的关键是消除重复计算.其中有一种技术是备忘录技术.

    可以用一个表将计算过的中间结果保存起来，在计算之前查表看看是否已经计算过

    在递归调用之前，先查找表中是否已有部分找零的最优解
    如果有，直接返回最优解而不进行递归调用
    如果没有，才进行递归调用
    """
    min_len = money_value
    print(know_results)
    if money_value in coin_value_list:
        return 1
    elif know_results[money_value] != 0:
        return know_results[money_value]
    else:
        for i in [c for c in coin_value_list if c < money_value]:
            now_len = 1 + recDc(coin_value_list, money_value - i, know_results)

            if now_len < min_len:
                min_len = now_len
                know_results[money_value] = now_len
                print(know_results)
    return min_len


# 动态规划
def getMinCountsLoop(k, values):
    # “新款”状态备忘录，用数组 memo 来表示（通常将其称之为 DP 数组，DP 是 Dynamic Programming 的缩写即动态规划）
    memo = [-1] * (k + 1)
    memo[0] = 0  # 初始化状态

    for item in range(1, k + 1):  # 当目标兑换金额为 item 时，至少需要 memo[item] 枚硬币才能凑出。
        minCount = k + 1  # 模拟无穷大
        for iter in range(len(values)):
            currentValue = values[iter]
            # 如果当前面值大于硬币总额，那么跳过
            if currentValue > item:
                continue

            # 使用当前面值，得到剩余硬币总额
            rest = item - currentValue
            restCount = memo[rest]

            # 如果返回-1，说明组合不可信，跳过
            if restCount == -1:
                continue

            # 保留最小总额
            itemCount = 1 + restCount
            if itemCount < minCount:
                minCount = itemCount

        # 如果是可用组合，记录结果
        if minCount != k + 1:
            memo[item] = minCount

    return memo[k]


def getMinCounts(k, values):
    memo = [-1] * (k + 1)
    memo[0] = 0  # 初始化状态
    for item in range(1, k + 1):
        memo[item] = k + 1

    for item in range(1, k + 1):
        for coin in values:
            if item - coin < 0:
                continue
            memo[item] = min(memo[item], memo[item - coin] + 1)  # 作出决策

    return memo[k]


if __name__ == '__main__':
    # get_min_coins(63)
    # print(recMC([1, 5, 10, 20, 50, 100], 63))  # 这个程序执行的太慢了.一共需要执行 39,024,572 次 .
    # print(recDc([1, 5, 10, 20, 50, 100], 63, [0] * 64))

    some_money = 63
    print(getMinCountsLoop(some_money, [1, 5, 10, 20, 50, 100]))
    print(getMinCounts(some_money, [1, 5, 10, 20, 50, 100]))
